#include "Skinner_Incremental.h"
#include "Log.h"
#include <limits>       // std::numeric_limits


Skinner_Incremental::Skinner_Incremental(int extreme_size) {
    extreme_set_size   = extreme_size;
}

// This method approximates the extreme set, by picking one initially,
// and updating it incrementally, in a greedy fashion.
//
// We start with a subset of the objects (of size k).  They will be our
// intial estimate of the extreme subset E.  Then, we visit each of the
// remaining objects a, and if it is far away, it becomes extreme, and
// gets added to E, and one member of e is taken out.
//
// How can we tell if a should be added and another e removed?  Well, if
// the new guy is the mediod, don't add it.  Otherwise, find the mediod
// and remove it.
//
// Thus, this resembles the Cored_Skinner class, which keeps removing
// mediods.  However, the medioids removed are medioids of the currently-
// extreme set, not medioids of a random subset of k objects.  So the whole
// algorithm may take O(k^2 * n) time, since we need O(k^2) distance calcs
// to find the medioid of k things.
//
// We could improve performance to O(k*n), thus:
// Initially, pick k items, and compute their all-to-all distances
// (takes O(k^2)).  Since medioids are identified by their average distance
// to all other objects, or, equivalently, by their total distance to all
// others, we could store the total distance for each object in E.  Then
// we could update this distance with each change to E.  This would take
// k adds, k subtracts to update the sums, then k compares to find the
// smallest sum. That is, O(k) per update, for a total of O(k^2 + k*(n-k))
// = O(k*n) overall.
//
std::pair<LMO_Span*,LMO_Span*> Skinner_Incremental::separate(LMO_Span& span) {
    LOG_ENTER(SKIN,"Skinner_Incremental::separate");

    int n = span.n;
    // First, grab the items into an array
    LMO_Iterator iter = span.start;
    LMO_Iterator *items = new LMO_Iterator[n];
    double *total_distance = new double[extreme_set_size + 1];
    for (int i=0; i<n; i++) {
        items[i] = iter++;
    }
    // randomize the array.
    std::random_shuffle(items, items + n);

    // Process objects within the array, dividing the array into parts:
    // First part: the extreme set E (0 through k)
    // Second part: objects yet to be considered.
    // Last part: discarded medioids.  These will be interior points.
    // BTW, k is extreme_set_size here.

    // Preprocess: compute initial distance totals within initial set E
    for (int i=0; i<extreme_set_size; i++) {
        for (int j=0; j<extreme_set_size; j++) {
            if (i == j) continue; // skip self-comparisons
            total_distance[i] += (*items[i])->distance(*items[j]);
        }
    }

    // Main process: visit each remaining obj, place in E or S-E.
    int first_extreme  = 0; // last extreme is k-1, always
    int next;               // next one being considered

    for (next = extreme_set_size; next < n; next++) {
        // Tentatively add next to E, and update totals of objs in E
        for (int i=0; i<extreme_set_size; i++) {
            total_distance[i] += (*items[i])->distance(*items[next]);
        }
        // and get total for next, too.
        total_distance[next] = 0;
        for (int i=0; i<extreme_set_size; i++) {
            total_distance[next] += (*items[next])->distance(*items[i]);
        }

        // now find mediod in E
        double min_tot_dist = std::numeric_limits<int>::max();
        int i_medioid;
        for (int i=0; i<extreme_set_size; i++) {
            if (total_distance[i] < min_tot_dist) {
                min_tot_dist = total_distance[i];
                i_medioid    = i;
            }
        }

        // Is the mediod in E more "mediod" than next?
        if (total_distance[i_medioid] < total_distance[next]) {
            // yes, swap out of E
            LMO_Iterator tmp = items[i_medioid];
            items[i_medioid] = items[next];
            items[next]      = tmp;
            total_distance[i_medioid] = total_distance[next];
        }
    }

    // Now, copy objects into extreme and interior sets
    Object_List *new_items = new Object_List();
    LMO_Span *interior;
    LMO_Span *extreme;
    LMO_Iterator last_extreme_item;
    for (int i=first_extreme; i<extreme_set_size; i++) {
        new_items.append(*(items[i]));
        if (i == extreme_set_size - 1)
            interior = new LMO_Span(new_items.begin(),
    }

    for (int i=extreme_set_size; i<n; i++) {
        cluster->interior_set.append(*(items[i]));
    }

    delete[] items;
    delete[] total_distance;
}

